#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

/* 递推：减而治之，子问题
 * n规模与n-1规模的关系
 * 约瑟夫环
 * （第m-1个数已经去掉重新编号 m+1为1）
 * 旧编号：m m+1 m+2 ...... m-2
 * 新编号：0  1   2  ...... n-1
 *则可以推导出 f(n,m) = (f(n-1,m)+m)%n


class Solution
{
 public:
  int lastRemaining(int n, int m)
  {
    if (n == 1) return 0;  // 只有一个数，返回索引0
    return (lastRemaining(n - 1, m) + m) % n;
  }
};
*/

// 循环链表
struct listnode
{
  int val;
  listnode* pnext;

  listnode(int v) : val(v), next(NULL) {}
};

class Solution
{
 public:
  int lastRemaining(int n, int m)
  {
    listnode* head = new listnode(0);
    listnode* l = head;
    listnode* pre = new listnode(0);

    for (int i = 1; i < n; ++i)
    {
      l->pnext = new listnode(i);
      l = l->next;
      if (i == n - 1)
      {
        pre = l;
        l->pnext = head;
      }
    }  // 循环链表已经创建好了

    l = head;
    while (l->pnext != l)  // 遍历循环列表
    {
      for (int i = 1; i < m; ++i)
      {
        pre = l;       // 当i=m-1, pre指向m-1
        l = l->pnext;  // l指向m
      }

      pre->pnext = l->pnext;
      listnode* temp = l;
      l = l->pnext;
      delete temp;
    }

    return l->val;
  }
};
